package b_sort.a_5_merge_sort;

import static b_sort.StringUtils.printArr;

/**
 * 归并排序
 * 时间复杂度    O(nlog2(n))
 * 空间复杂度    O(n)
 * 稳定性       稳定
 * ------
 * 思路：开始每个元素单独作为子序列，每轮进行相邻子序列归并，直到归并为1个序列
 * (自底向上思考方式，可以循环实现，非递归)
 * (自顶向下思考方式，可以递归实现)
 * @author FRSF
 * @since 2025/3/2 21:03
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {3, 8, 1, 5, 10, 6, 7, 2, 9, 4};
        mergeSort(arr);
    }

    private static void mergeSort(int[] arr) {
        printArr(arr);
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        printArr(arr);
    }

    // 递归排序
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;    // 找到中间点
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    // 合并两个有序数组
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 左半部分的起始索引
        int j = mid + 1; // 右半部分的起始索引
        int k = 0; // 临时数组的起始索引

        while (i <= mid && j <= right) {
            temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        k = 0;
        while (left <= right) {
            arr[left++] = temp[k++];
        }
    }
}
